import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-23
 * Time: 15:28
 */
public class Solution {
    public int numTilePossibilities(String tiles) {
        Set<String> set = new HashSet<>();
        int[] mark = new int[tiles.length()];
        StringBuilder stringBuilder = new StringBuilder();
        dfs(tiles, mark, set, stringBuilder);
        return set.size();
    }

    public void dfs(String tiles, int[] mark, Set<String> set,
                    StringBuilder stringBuilder ){
        if(stringBuilder.length() > 0){
            set.add(stringBuilder.toString());
        }
        if(stringBuilder.length() == tiles.length()){
            return;
        }
        for (int i = 0; i < tiles.length(); i++) {
            if(mark[i] == 0){
                stringBuilder.append(tiles.charAt(i));
                mark[i] = 1;
                dfs(tiles, mark, set, stringBuilder);
                mark[i] = 0;
                stringBuilder.delete(stringBuilder.length() - 1, stringBuilder.length());
            }
        }
    }
}
